package me.algo;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

/**
 * @author guozheng
 * @date 2024/3/17
 */
public class Main {
    public static void main(String[] args) {
//        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7};
//        rotate(nums,3);
        HashSet<Integer> set = new HashSet<>();
        boolean add = set.add(1);
        boolean add1 = set.add(1);
        System.out.println(add);
        System.out.println(add1);
        ListNode a = numToList(942);
        ListNode b = numToList(9465);
        ListNode listNode = addTwoNumbers(a, b);
        int i = listToNum(listNode);
        System.out.println(listNode);
        System.out.println(i);


//        TreeNode node = new TreeNode(2, new TreeNode(9), new TreeNode(20, new TreeNode(15, new TreeNode(7))));
//        int i1 = maxDepth(node);
//        System.out.println(i1);
        TreeNode node = new TreeNode(5, new TreeNode(4), new TreeNode(6, new TreeNode(3), new TreeNode(7)));
        List<Integer> res =  new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode cursor = node;
        while(cursor != null || !stack.isEmpty()) {
            while (cursor != null) {
                stack.push(cursor);
                cursor = cursor.left;
            }
            TreeNode pop = stack.pop();
            res.add(pop.val);
            cursor = pop.right;
        }
        System.out.println(res);
        System.out.println(countNodes(node));
    }
    public static int countNodes(TreeNode root) {
        int total = 0;
        LinkedList<TreeNode> nodes = new LinkedList<>();
        nodes.addLast(root);
        while(!nodes.isEmpty()) {
            int size = nodes.size();
            while(size > 0) {
                size--;
                TreeNode n = nodes.removeFirst();
                total++;
                if (n.left != null) {
                    nodes.addLast(n.left);
                }
                if (n.right != null) {
                    nodes.addLast(n.right);
                }
            }
        }
        return total;
    }
    public static class TreeNode {

        int val;
        TreeNode left;
        TreeNode right;


        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public static int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int depth = 1;
        LinkedList<TreeNode> ls = new LinkedList<TreeNode>();
        ls.addFirst(root);
        while(!ls.isEmpty()) {
            int size = ls.size();
            while (size > 0) {
                TreeNode tn = ls.removeFirst();
                if (tn.left != null) {
                    ls.addLast(tn.left);
                }
                if (tn.right != null) {
                    ls.addLast(tn.right);
                }
                size--;
            }
            depth++;
        }
        return depth;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int x = listToNum(l1);
        int y = listToNum(l2);
        int z = x + y;
        return numToList(z);
    }

    static ListNode numToList(int num) {
        ListNode node = new ListNode();
        ListNode c = node;
        int x = num;
        do {
            int v = x % 10;
            c.next = new ListNode(v);
            c = c.next;
            x = x / 10;
        } while (x > 0);
        return node.next;
    }

    static int listToNum(ListNode node) {
        int x = 0;
        new LinkedList<>();
        while (node != null) {
            x = x * 10 + node.val;
            node = node.next;
        }
        return x;
    }

    public static void rotate(int[] nums, int k) {
        if (nums == null || nums.length <= 1) {
            return;
        }

        int len = nums.length;

        int z = k % len;
        int[] ks = new int[z];
        for (int i = 0; i < z; i++) {
            ks[i] = nums[len - z + i];
        }
        for (int x = len - 1; x >= z; x--) {
            nums[x] = nums[x-z];
        }
        for (int p = 0; p < z; p++) {
            nums[p] = ks[p];
        }
    }
    void swap(int[] nums,int j,int k) {
        int z = nums[j];
        nums[j] = nums[k];
        nums[k] = z;
    }
}
